package demo_leetcode_day;

/*
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
*/

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class demo_20200730 {
    public static void main(String[] args) {
        System.out.println(new Solution().integerBreak(10));
    }


    static class Solution {
        /**
         * 思路，以下方法超时，再优化
         * 比如dp是每个数乘积最大化的值dp[2] = 1,dp[5] = 6
         * 如果10拆分成 5 + 5，则最大就是 dp[5] * dp[5] = 36
         * 然后，因为存在dp[2] = 1这种，乘积比自身还小的情况所以要考虑自身，比如 4 = 2+2，如果 dp[2] * dp[2] = 1，而 2*2=4
         */
        Map<Integer, Integer> mapDp = new HashMap<>();
        public int integerBreak(int n) {
            mapDp.put(1, 1);
            mapDp.put(2, 1);
            mapDp.put(3, 2);
            mapDp.put(4, 4);
            return findMax(n);
        }
        private int findMax(Integer num) {
            // 包含则直接返回
            if (mapDp.containsKey(num)) return mapDp.get(num);
            // 不包含
            int maxRet = 0;
            for (int i = 1; i < num; i++) {
                int maxI = Math.max(findMax(i), i);
                int maxJ = Math.max(findMax(num - i), num - i);
                maxRet = Math.max(maxRet, maxI * maxJ);
            }
            if (!mapDp.containsKey(num)) mapDp.put(num, maxRet);
            return maxRet;
        }
    }

//    static class Solution {
//        /**
//         * 思路，递归的方式处理
//         * 追加，直接不行，修改进行优化
//         */
//        int retMax = 0; // 结果，最大值
//
//        public int integerBreak(int n) {
//            Stack<Integer> list = new Stack<>();
//            findMax(n, list);
//            return retMax;
//        }
//
//        private void findMax(Integer num, Stack<Integer> list) {
//            // 结束条件
//            if (num == 0) {
//                if (list.size() == 1) return;
//                // 计算乘积
//                int product = 0;
//                for (Integer number : list) {
//                    if (product == 0) {
//                        product = number;
//                    } else {
//                        product *= number;
//                    }
//                }
//                retMax = Math.max(retMax, product);
//                return;
//            }
//            // 每个数字进行遍历
//            for (int i = num; i > 0; i--) {
//                list.push(i);
//                findMax(num - i, list);
//                list.pop();
//            }
//        }
//    }

//    static class Solution {
//        /**
//         * 思路，实际上，尽量均分即可，输入值N给一个除数，要求除数的结果和除数尽量相近即可
//         * （乘法的话，需要尽量每个数最大，所以比如10，尽量平均分配的话，就是3+3+4）
//         */
//        public int integerBreak(int n) {
//            if (n == 2) return 1;
//            int divider = 1;
//            double diff = Double.MAX_VALUE;
//            for (int i = 2; i <= (n / 2) + ((n % 2) == 0 ? 0 : 1); i++) {
//                double curDiff = Math.abs(n / i - i);
//                if (curDiff >= diff) {
//                    break;
//                } else {
//                    diff = curDiff;
//                    divider = i;
//                }
//            }
//            // 乘积计算
//            int remainder = n % divider; // 余数，平均分配给
//            int sum = n / divider;
//            for (int i = 1; i < divider; i++) {
//                sum *= ((n / divider) + (divider - i <= remainder?1:0));
//            }
//            return sum;
//        }
//    }
}
